#include <iostream>
#include <vector>

using namespace std;

int partition(vector<int>& nums, int left, int right) // nums参数也需要设置为引用,因为这个分区函数不仅仅是找到分界点,还需要对数组进行了一些排序操作
{
    /**
     * 对于一个序列nums,只操作[left,right]范围内的数;
     * 将大的数放右边,小的数放左边;并返回最终的分界点位置;
     * 注意:这里的 left 和 right 都是下标+1;
     */
    int sep_key = nums[left - 1]; // 用这个 nums 序列的第一个元素作为最终的分界点;之后一直是这个值;只不过这个值的位置会变动;
    while (left < right)
    {
        // 进行交替扫描;
        while (left < right && nums[right - 1] >= sep_key)
        {
            // 说明当前的 right 对应的值应该在sep_key的右侧,是符合要去的
            right--;
        }
        swap(nums[left - 1], nums[right - 1]); // 注意:交换的是 left 和 right 对应位置的元素;
        // 以初始交换为例;完成上面一行的交换之后,分界点的值被交换到后面去了;此时分界点右侧都是比分界点大的;
        // 下面就要看左侧有没有比分界点大的数,有的话就再交换一下
        while (left < right && nums[left - 1] <= sep_key)
        {
            left++;
        }
        // 此时找到了左边第一个比分界点值大的数;那就需要再次交换;
        swap(nums[left - 1], nums[right - 1]); // 交换的代码是和上面的交换一样的;
        // 可以发现,在交替交换时,不是 left 指向分界点,就是 right 指向分界点
    }
    return left; // left==right 时左边都是比分界点小的,右边都是比分界点大的
}

void QSort(vector<int>& nums, int left, int right)
{
    /**
     * 该递归的思路:通过调用 partition 函数将大的数放右边,小的数放左边;之后再递归就是分别去看左右两个部分;
     * 然后继续对左右两边的子序列进行分区;直到左右序列无法再进行分区为止
     */
    int partition_position;
    if (left < right)
    {
        // 如果分区之后的子序列不止一个元素,则继续进行递归
        partition_position = partition(nums, left, right); // 使用partition函数将数组大的数放到右边,小的数放到左边;并返回分界点的位置
        QSort(nums, left, partition_position-1);
        QSort(nums, partition_position + 1, right);
    }
}

int main(){
    vector<int> nums = {50, 10, 90, 30, 70, 40, 80, 60, 20};
    QSort(nums,1,nums.size());
    

    for (int i = 0; i < nums.size(); i++)
    {
        cout<<nums[i]<<",";
    }
    cout<<endl;
    return 0;
}